package io.github.consoles.dsa;

import java.util.Iterator;

/**
 * Created by yiihua-013 on 17/1/21.
 * <p>
 * 自动扩容的栈:数组实现
 * <p>
 * 这个实现中栈永远不会溢出,使用率也不会低于四分之一。动态调整数组数组大小以保持数组大小和栈大小的比小于一个常数
 * <p>
 * 该实现几乎达到了任意数据类型实现的最佳性能
 * <p>
 * 1.每项操作的用时都和集合大小无关;
 * 2.空间需求总是不超过集合大小乘以一个常数。
 * <p>
 * 缺点在于某些push和pop会调整数组的大小,这项操作的耗时和栈的大小成正比
 */
public class ArrayStack<Item> implements Iterable<Item> {

    private Item[] arr;
    private int    size;

    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 创建一个具有初始容量的栈
     *
     * @param cap
     */
    public ArrayStack(int cap) {
        arr = (Item[]) new Object[cap]; // 创建泛型数组在java中是不允许的
    }

    public ArrayStack() {
        this(DEFAULT_CAPACITY);
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void push(Item item) {
        // check if stack is full
        if (size == arr.length) resize(2 * arr.length); // 数组扩容
        arr[size++] = item;
    }

    /**
     * 将大小为n <= max的栈移动到一个新的大小为max的栈
     *
     * @param max
     */
    private void resize(int max) {
        Item[] temp = (Item[]) new Object[max];
        for (int i = 0; i < size; i++) temp[i] = arr[i];
        arr = temp;
    }

    public Item pop() {
//        Item item = arr[size-1];
//        arr[size-1] = null; // gc
//        size--;
//        return item;
        Item item = arr[--size];
        arr[size] = null; // gc
        // 数组太长我们就将其长度减半。检测条件为栈大小是否小于数组的四分之一
        // 这时的栈为半满,在下次改变数组大小之前可以多次进行push和pop
        if (size > 0 && size == arr.length / 4) resize(arr.length / 2);
        return item;
    }

    public Item peek() {
        return arr[size - 1];
    }

    public static <T> ArrayStack<T> copy(ArrayStack<T> stack) {
        // 由于栈是逆向的迭代器,所以需要一个中间栈,顺序颠倒2次就和原来的一样了
        ArrayStack<T> result = new ArrayStack<>();
        ArrayStack<T> tmp    = new ArrayStack<>();
        for (T item : stack) {
            tmp.push(item);
        }
        for (T item : tmp) {
            result.push(item);
        }
        return result;
    }

    @Override
    public Iterator<Item> iterator() {
        return new ReserseArrayIterator();
    }

    private class ReserseArrayIterator implements Iterator<Item> {

        private int count = size;

        @Override
        public boolean hasNext() {
            return count > 0;
        }

        @Override
        public Item next() {
            return arr[--count];
        }
    }
}
